#include<bits/stdc++.h>

using namespace std;
const int MAXN = 101;
const int INF = 1e9;
int a[MAXN][MAXN];
int book[MAXN];
int dis[MAXN];
int n, m;

/***
 * Dijkstra算法计算单源点的最短路径，需要图是正权图（每一条边都是正数）算法复杂度O(n^2)
 * @param s
 */
void Dijkstra(int s) {
    for (int i = 1; i <= n; i++) {
        book[i] = 0;
        dis[i] = a[s][i];
    }
    book[s] = 1;///第一个点加入了确定最短路径的集合中

    for (int i = 1; i < n; i++) {
        ///找到离源点最近的点，加入到集合中
        int u = 1, MIN = INF;
        for (int j = 1; j <= n; j++) {
            if (book[j] == 0 && dis[j] < MIN) {/// 找dis数组中权值最小的点
                u = j;///待加入的点
                MIN = dis[j];
            }
        }
        book[u] = 1;//add u into selected set
        for (int j = 1; j <= n; j++) {
            if (book[j] == 0 && a[u][j] < INF && dis[j] > dis[u] + a[u][j]) {
                dis[j] = dis[u] + a[u][j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    cout << endl;
}

int main() {
    ifstream cin("graph.in");
    cin >> n >> m;
    ///初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                a[i][j] = 0;
            } else {
                a[i][j] = INF;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        if (z < a[x][y])
            a[x][y] = a[y][x] = z;
    }
    Dijkstra(1);
    return 0;
}
/*

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4

*/
